package com.hqq.exercise.math;

import com.hqq.exercise.list.ListNode;

/**
 * Josephuse 约瑟夫环
 * 题目描述:
 * 0,1，...,n-1这n个数排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字
 * 思路1:
 * 环形链表模拟圆圈
 * 思路2:
 * 找数字的规律
 * f(n,m) = {
 * 0 ,  n=1
 * [f(n-1,m)+m]%n , n>1
 * }
 * Created by heqianqian on 2017/8/23.
 */
public class Josephuse {

    public static void main(String[] args) {
        int[] array = new int[]{0, 1, 2, 3, 4};
        int remain = executeWithDList(array, 3);
        System.out.println(remain);

        remain = executeWithDList(13, 3);
        System.out.println(remain);

        remain = execute(13, 3);
        System.out.println(remain);
    }

    public static int execute(int n, int m) {
        if (n == 1) {
            return 0;
        }
        return (execute(n - 1, m) + m) % n;
    }

    public static int executeWithDList(int n, int m) {
        //建立环形链表
        return del(buildCircleList(n), m);
    }

    public static int executeWithDList(int[] array, int m) {
        if (array == null || array.length == 0 || m < 0 || m > array.length) {
            return -1;
        }
        //建立环形链表
        return del(buildCircleList(array), m);
    }

    private static int del(ListNode circleList, int m) {
        while (circleList.next != circleList) {//链表中最后只剩一个元素
            for (int i = 0; i < m - 1; i++) {
                circleList = circleList.next;
            }
            circleList.data = circleList.next.data;
            circleList.next = circleList.next.next;
        }
        return circleList.data;
    }

    /**
     * 构建环形链表
     */
    private static ListNode buildCircleList(int[] array) {
        ListNode head = new ListNode(array[0]);
        ListNode node = head;
        for (int i = 1; i < array.length; i++) {
            ListNode temp = new ListNode(array[i]);
            node.next = temp;
            node = temp;
        }
        node.next = head;
        return head;
    }

    private static ListNode buildCircleList(int n) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i = 1; i < n; i++) {
            ListNode temp = new ListNode(i);
            node.next = temp;
            node = temp;
        }
        node.next = head;
        return head;
    }

}
